package leetcode.datastruct1;

import java.util.*;

/*
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
注意：每个函数都应当满足 O(1) 平均时间复杂度。



示例：

输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]

解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"


提示：

1 <= key.length <= 10
key 由小写英文字母组成
测试用例保证：在每次调用 dec 时，数据结构中总存在 key
最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 104 次
 */
public class LeetCode432_AllOne {

    private Map<Integer, Bucket> freqMap = new HashMap<>();
    private Map<String, Integer> keyFreq = new HashMap<>();
    private Bucket minBucket = new Bucket(0);
    private Bucket maxBucket = new Bucket(Integer.MAX_VALUE);
    static class Bucket {
        int freq;
        Bucket pre;
        Bucket next;

        Set<String> s = new HashSet<>();

        public Bucket(int freq) {
            this.freq = freq;
        }
        public void add(String key) {
            s.add(key);
        }
        public void remove(String key) {
            s.remove(key);
        }
        public int getFreq() {
            return freq;
        }
    }

    public LeetCode432_AllOne() {
        minBucket.next = maxBucket;
        maxBucket.pre = minBucket;
    }

    public void inc(String key) {
        // 存在
        if (keyFreq.containsKey(key)) {
            Integer freq = keyFreq.get(key);
            Bucket bucket = freqMap.get(freq);

            Bucket nextFreq = bucket.next;
            if (nextFreq.getFreq() == freq + 1) {
                bucket.remove(key);
                nextFreq.next.add(key);
                keyFreq.put(key, freq + 1);
            }else {
                bucket.remove(key);
                nextFreq = new Bucket(freq + 1);
                nextFreq.add(key);

                Bucket next = bucket.next;
                bucket.next = nextFreq;
                nextFreq.pre = bucket;
                nextFreq.next = next;
                next.pre = nextFreq;

                freqMap.put(freq + 1, nextFreq);
                keyFreq.put(key, freq + 1);
            }
            if (bucket.s.isEmpty()) {
                freqMap.remove(freq);

                bucket.pre.next = bucket.next;
                bucket.next.pre = bucket.pre;
                bucket.pre = null;
                bucket.next = null;
            }
        }else {
            Bucket bucket = freqMap.get(1);
            if (bucket == null) {
                bucket = new Bucket(1);
                bucket.add(key);

                Bucket next = minBucket.next;
                minBucket.next = bucket;
                bucket.pre = minBucket;
                bucket.next = next;
                next.pre = bucket;

                freqMap.put(1, bucket);
            }else {
                bucket.add(key);
            }
            keyFreq.put(key, 1);
        }
    }

    public void dec(String key) {

    }

    public String getMaxKey() {
        return "";
    }

    public String getMinKey() {
        return "";
    }

    public static void main(String[] args) {
        LeetCode432_AllOne leetCode432AllOne = new LeetCode432_AllOne();
        leetCode432AllOne.inc("a");
        leetCode432AllOne.inc("a");
        leetCode432AllOne.inc("b");
        leetCode432AllOne.inc("a");
        leetCode432AllOne.inc("c");
        leetCode432AllOne.inc("b");


    }
}
